{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GloVe: Global Vectors for Word2Vec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "c:\\users\\thushan\\documents\\python_virtualenvs\\tensorflow_venv\\lib\\site-packages\\h5py\\__init__.py:36: FutureWarning: Conversion of the second argument of issubdtype from `float` to `np.floating` is deprecated. In future, it will be treated as `np.float64 == np.dtype(float).type`.\n",
      "  from ._conv import register_converters as _register_converters\n"
     ]
    }
   ],
   "source": [
    "# These are all the modules we'll be using later. Make sure you can import them\n",
    "# before proceeding further.\n",
    "%matplotlib inline\n",
    "from __future__ import print_function\n",
    "import collections\n",
    "import math\n",
    "import numpy as np\n",
    "import os\n",
    "import random\n",
    "import tensorflow as tf\n",
    "import bz2\n",
    "from matplotlib import pylab\n",
    "from six.moves import range\n",
    "from six.moves.urllib.request import urlretrieve\n",
    "from sklearn.manifold import TSNE\n",
    "from sklearn.cluster import KMeans\n",
    "from scipy.sparse import lil_matrix\n",
    "import nltk # standard preprocessing\n",
    "import operator # sorting items in dictionary by value\n",
    "#nltk.download() #tokenizers/punkt/PY3/english.pickle\n",
    "from math import ceil"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dataset\n",
    "This code downloads a [dataset](http://www.evanjones.ca/software/wikipedia2text.html) consisting of several Wikipedia articles totaling up to roughly 61 megabytes. Additionally the code makes sure the file has the correct size after downloading it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found and verified wikipedia2text-extracted.txt.bz2\n"
     ]
    }
   ],
   "source": [
    "url = 'http://www.evanjones.ca/software/'\n",
    "\n",
    "def maybe_download(filename, expected_bytes):\n",
    "  \"\"\"Download a file if not present, and make sure it's the right size.\"\"\"\n",
    "  if not os.path.exists(filename):\n",
    "    filename, _ = urlretrieve(url + filename, filename)\n",
    "  statinfo = os.stat(filename)\n",
    "  if statinfo.st_size == expected_bytes:\n",
    "    print('Found and verified %s' % filename)\n",
    "  else:\n",
    "    print(statinfo.st_size)\n",
    "    raise Exception(\n",
    "      'Failed to verify ' + filename + '. Can you get to it with a browser?')\n",
    "  return filename\n",
    "\n",
    "filename = maybe_download('wikipedia2text-extracted.txt.bz2', 18377035)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Read Data with Preprocessing with NLTK\n",
    "Reads data as it is to a string, convert to lower-case and tokenize it using the nltk library. This code reads data in 1MB portions as processing the full text at once slows down the task and returns a list of words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reading data...\n",
      "Data size 3360286\n",
      "Example words (start):  ['propaganda', 'is', 'a', 'concerted', 'set', 'of', 'messages', 'aimed', 'at', 'influencing']\n",
      "Example words (end):  ['favorable', 'long-term', 'outcomes', 'for', 'around', 'half', 'of', 'those', 'diagnosed', 'with']\n"
     ]
    }
   ],
   "source": [
    "def read_data(filename):\n",
    "  \"\"\"\n",
    "  Extract the first file enclosed in a zip file as a list of words\n",
    "  and pre-processes it using the nltk python library\n",
    "  \"\"\"\n",
    "\n",
    "  with bz2.BZ2File(filename) as f:\n",
    "\n",
    "    data = []\n",
    "    file_size = os.stat(filename).st_size\n",
    "    chunk_size = 1024 * 1024 # reading 1 MB at a time as the dataset is moderately large\n",
    "    print('Reading data...')\n",
    "    for i in range(ceil(file_size//chunk_size)+1):\n",
    "        bytes_to_read = min(chunk_size,file_size-(i*chunk_size))\n",
    "        file_string = f.read(bytes_to_read).decode('utf-8')\n",
    "        file_string = file_string.lower()\n",
    "        # tokenizes a string to words residing in a list\n",
    "        file_string = nltk.word_tokenize(file_string)\n",
    "        data.extend(file_string)\n",
    "  return data\n",
    "\n",
    "words = read_data(filename)\n",
    "print('Data size %d' % len(words))\n",
    "token_count = len(words)\n",
    "\n",
    "print('Example words (start): ',words[:10])\n",
    "print('Example words (end): ',words[-10:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Building the Dictionaries\n",
    "Builds the following. To understand each of these elements, let us also assume the text \"I like to go to school\"\n",
    "\n",
    "* `dictionary`: maps a string word to an ID (e.g. {I:0, like:1, to:2, go:3, school:4})\n",
    "* `reverse_dictionary`: maps an ID to a string word (e.g. {0:I, 1:like, 2:to, 3:go, 4:school}\n",
    "* `count`: List of list of (word, frequency) elements (e.g. [(I,1),(like,1),(to,2),(go,1),(school,1)]\n",
    "* `data` : Contain the string of text we read, where string words are replaced with word IDs (e.g. [0, 1, 2, 3, 2, 4])\n",
    "\n",
    "It also introduces an additional special token `UNK` to denote rare words to are too rare to make use of."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Most common words (+UNK) [['UNK', 69215], ('the', 226881), (',', 184013), ('.', 120944), ('of', 116323)]\n",
      "Sample data [1730, 9, 8, 16741, 223, 4, 5169, 4509, 26, 11641]\n"
     ]
    }
   ],
   "source": [
    "# we restrict our vocabulary size to 50000\n",
    "vocabulary_size = 50000 \n",
    "\n",
    "def build_dataset(words):\n",
    "  count = [['UNK', -1]]\n",
    "  # Gets only the vocabulary_size most common words as the vocabulary\n",
    "  # All the other words will be replaced with UNK token\n",
    "  count.extend(collections.Counter(words).most_common(vocabulary_size - 1))\n",
    "  dictionary = dict()\n",
    "\n",
    "  # Create an ID for each word by giving the current length of the dictionary\n",
    "  # And adding that item to the dictionary\n",
    "  for word, _ in count:\n",
    "    dictionary[word] = len(dictionary)\n",
    "    \n",
    "  data = list()\n",
    "  unk_count = 0\n",
    "  # Traverse through all the text we have and produce a list\n",
    "  # where each element corresponds to the ID of the word found at that index\n",
    "  for word in words:\n",
    "    # If word is in the dictionary use the word ID,\n",
    "    # else use the ID of the special token \"UNK\"\n",
    "    if word in dictionary:\n",
    "      index = dictionary[word]\n",
    "    else:\n",
    "      index = 0  # dictionary['UNK']\n",
    "      unk_count = unk_count + 1\n",
    "    data.append(index)\n",
    "    \n",
    "  # update the count variable with the number of UNK occurences\n",
    "  count[0][1] = unk_count\n",
    "  \n",
    "  reverse_dictionary = dict(zip(dictionary.values(), dictionary.keys())) \n",
    "  # Make sure the dictionary is of size of the vocabulary\n",
    "  assert len(dictionary) == vocabulary_size\n",
    "    \n",
    "  return data, count, dictionary, reverse_dictionary\n",
    "\n",
    "data, count, dictionary, reverse_dictionary = build_dataset(words)\n",
    "print('Most common words (+UNK)', count[:5])\n",
    "print('Sample data', data[:10])\n",
    "del words  # Hint to reduce memory."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generating Batches of Data for GloVe\n",
    "Generates a batch or target words (`batch`) and a batch of corresponding context words (`labels`). It reads `2*window_size+1` words at a time (called a `span`) and create `2*window_size` datapoints in a single span. The function continue in this manner until `batch_size` datapoints are created. Everytime we reach the end of the word sequence, we start from beginning. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "data: ['propaganda', 'is', 'a', 'concerted', 'set', 'of', 'messages', 'aimed']\n",
      "\n",
      "with window_size = 2:\n",
      "    batch: ['a', 'a', 'a', 'a', 'concerted', 'concerted', 'concerted', 'concerted']\n",
      "    labels: ['propaganda', 'is', 'concerted', 'set', 'is', 'a', 'set', 'of']\n",
      "    weights: [0.5, 1.0, 1.0, 0.5, 0.5, 1.0, 1.0, 0.5]\n",
      "\n",
      "with window_size = 4:\n",
      "    batch: ['set', 'set', 'set', 'set', 'set', 'set', 'set', 'set']\n",
      "    labels: ['propaganda', 'is', 'a', 'concerted', 'of', 'messages', 'aimed', 'at']\n",
      "    weights: [0.25, 0.33333334, 0.5, 1.0, 1.0, 0.5, 0.33333334, 0.25]\n"
     ]
    }
   ],
   "source": [
    "data_index = 0\n",
    "\n",
    "def generate_batch(batch_size, window_size):\n",
    "  # data_index is updated by 1 everytime we read a data point\n",
    "  global data_index \n",
    "    \n",
    "  # two numpy arras to hold target words (batch)\n",
    "  # and context words (labels)\n",
    "  batch = np.ndarray(shape=(batch_size), dtype=np.int32)\n",
    "  labels = np.ndarray(shape=(batch_size, 1), dtype=np.int32)\n",
    "  weights = np.ndarray(shape=(batch_size), dtype=np.float32)\n",
    "\n",
    "  # span defines the total window size, where\n",
    "  # data we consider at an instance looks as follows. \n",
    "  # [ skip_window target skip_window ]\n",
    "  span = 2 * window_size + 1 \n",
    "    \n",
    "  # The buffer holds the data contained within the span\n",
    "  buffer = collections.deque(maxlen=span)\n",
    "  \n",
    "  # Fill the buffer and update the data_index\n",
    "  for _ in range(span):\n",
    "    buffer.append(data[data_index])\n",
    "    data_index = (data_index + 1) % len(data)\n",
    "  \n",
    "  # This is the number of context words we sample for a single target word\n",
    "  num_samples = 2*window_size \n",
    "\n",
    "  # We break the batch reading into two for loops\n",
    "  # The inner for loop fills in the batch and labels with \n",
    "  # num_samples data points using data contained withing the span\n",
    "  # The outper for loop repeat this for batch_size//num_samples times\n",
    "  # to produce a full batch\n",
    "  for i in range(batch_size // num_samples):\n",
    "    k=0\n",
    "    # avoid the target word itself as a prediction\n",
    "    # fill in batch and label numpy arrays\n",
    "    for j in list(range(window_size))+list(range(window_size+1,2*window_size+1)):\n",
    "      batch[i * num_samples + k] = buffer[window_size]\n",
    "      labels[i * num_samples + k, 0] = buffer[j]\n",
    "      weights[i * num_samples + k] = abs(1.0/(j - window_size))\n",
    "      k += 1 \n",
    "    \n",
    "    # Everytime we read num_samples data points,\n",
    "    # we have created the maximum number of datapoints possible\n",
    "    # withing a single span, so we need to move the span by 1\n",
    "    # to create a fresh new span\n",
    "    buffer.append(data[data_index])\n",
    "    data_index = (data_index + 1) % len(data)\n",
    "  return batch, labels, weights\n",
    "\n",
    "print('data:', [reverse_dictionary[di] for di in data[:8]])\n",
    "\n",
    "for window_size in [2, 4]:\n",
    "    data_index = 0\n",
    "    batch, labels, weights = generate_batch(batch_size=8, window_size=window_size)\n",
    "    print('\\nwith window_size = %d:' %window_size)\n",
    "    print('    batch:', [reverse_dictionary[bi] for bi in batch])\n",
    "    print('    labels:', [reverse_dictionary[li] for li in labels.reshape(8)])\n",
    "    print('    weights:', [w for w in weights])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating the Word Co-Occurance Matrix\n",
    "Why GloVe shine above context window based method is that it employs global statistics of the corpus in to the model (according to authors). This is done by using information from the word co-occurance matrix to optimize the word vectors. Basically, the X(i,j) entry of the co-occurance matrix says how frequent word i to appear near j. We also use a weighting mechanishm to give more weight to words close together than to ones further-apart (from experiments section of the paper)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(50000, 50000)\n",
      "Running 420035 iterations to compute the co-occurance matrix\n",
      "\tFinished 100000 iterations\n",
      "\tFinished 200000 iterations\n",
      "\tFinished 300000 iterations\n",
      "\tFinished 400000 iterations\n",
      "Sample chunks of co-occurance matrix\n",
      "\n",
      "Target Word: \"UNK\"\n",
      "Context word:\",\"(id:2,count:3482.30), \"UNK\"(id:0,count:2164.01), \"the\"(id:1,count:2020.93), \"and\"(id:5,count:1454.50), \".\"(id:3,count:1310.58), \"of\"(id:4,count:1086.33), \"(\"(id:13,count:1047.17), \")\"(id:12,count:831.17), \"in\"(id:6,count:776.17), \"a\"(id:8,count:624.50), \n",
      "\n",
      "Target Word: \"imagery\"\n",
      "Context word:\"and\"(id:5,count:1.25), \"UNK\"(id:0,count:1.00), \"generated\"(id:3145,count:1.00), \"demonstrates\"(id:10422,count:1.00), \"explored\"(id:5276,count:1.00), \"horrific\"(id:16241,count:1.00), \"(\"(id:13,count:1.00), \",\"(id:2,count:0.58), \"computer\"(id:936,count:0.50), \"goya\"(id:22688,count:0.50), \n",
      "\n",
      "Target Word: \"defining\"\n",
      "Context word:\"the\"(id:1,count:5.00), \"of\"(id:4,count:2.83), \"and\"(id:5,count:1.50), \"feature\"(id:1397,count:1.00), \"other\"(id:42,count:1.00), \"influence\"(id:452,count:1.00), \"it\"(id:24,count:1.00), \"or\"(id:29,count:1.00), \"than\"(id:62,count:1.00), \"moments\"(id:7053,count:1.00), \n",
      "\n",
      "Target Word: \"liberalism\"\n",
      "Context word:\"of\"(id:4,count:5.75), \".\"(id:3,count:3.25), \"forms\"(id:423,count:1.50), \"the\"(id:1,count:1.08), \"western\"(id:216,count:1.00), \"within\"(id:152,count:1.00), \"are\"(id:22,count:1.00), \"may\"(id:73,count:1.00), \"on\"(id:18,count:1.00), \"<\"(id:1716,count:1.00), \n",
      "\n",
      "Target Word: \"rampant\"\n",
      "Context word:\",\"(id:2,count:2.08), \"and\"(id:5,count:1.25), \"UNK\"(id:0,count:1.00), \"government\"(id:84,count:1.00), \"also\"(id:37,count:1.00), \"were\"(id:31,count:1.00), \"throughout\"(id:308,count:1.00), \".\"(id:3,count:1.00), \"the\"(id:1,count:0.83), \"expenditures\"(id:10039,count:0.50), \n",
      "\n",
      "Target Word: \"and\"\n",
      "Context word:\",\"(id:2,count:3990.46), \"the\"(id:1,count:2566.00), \"UNK\"(id:0,count:1488.59), \"of\"(id:4,count:1001.66), \".\"(id:3,count:894.16), \"in\"(id:6,count:728.16), \"to\"(id:7,count:555.67), \"a\"(id:8,count:549.25), \")\"(id:12,count:412.92), \"and\"(id:5,count:318.50), \n",
      "\n",
      "Target Word: \"in\"\n",
      "Context word:\"the\"(id:1,count:3765.79), \",\"(id:2,count:1934.93), \".\"(id:3,count:1836.76), \"UNK\"(id:0,count:776.17), \"of\"(id:4,count:747.16), \"and\"(id:5,count:723.41), \"a\"(id:8,count:685.08), \"to\"(id:7,count:425.67), \"in\"(id:6,count:316.00), \"was\"(id:11,count:290.08), \n",
      "\n",
      "Target Word: \"to\"\n",
      "Context word:\"the\"(id:1,count:2449.92), \",\"(id:2,count:990.33), \".\"(id:3,count:687.00), \"a\"(id:8,count:613.00), \"be\"(id:30,count:573.75), \"and\"(id:5,count:527.33), \"UNK\"(id:0,count:470.42), \"of\"(id:4,count:457.09), \"in\"(id:6,count:403.67), \"is\"(id:9,count:282.67), \n",
      "\n",
      "Target Word: \"a\"\n",
      "Context word:\",\"(id:2,count:1496.51), \"of\"(id:4,count:1298.42), \".\"(id:3,count:907.00), \"in\"(id:6,count:713.08), \"the\"(id:1,count:640.42), \"to\"(id:7,count:625.92), \"as\"(id:10,count:614.67), \"UNK\"(id:0,count:602.92), \"and\"(id:5,count:583.08), \"is\"(id:9,count:558.25), \n",
      "\n",
      "Target Word: \"is\"\n",
      "Context word:\"the\"(id:1,count:1062.00), \",\"(id:2,count:651.92), \".\"(id:3,count:567.50), \"a\"(id:8,count:504.00), \"it\"(id:24,count:381.92), \"of\"(id:4,count:340.67), \"UNK\"(id:0,count:298.83), \"to\"(id:7,count:261.42), \"in\"(id:6,count:237.42), \"and\"(id:5,count:232.08), \n"
     ]
    }
   ],
   "source": [
    "# We are creating the co-occurance matrix as a compressed sparse colum matrix from scipy. \n",
    "cooc_data_index = 0\n",
    "dataset_size = len(data) # We iterate through the full text\n",
    "skip_window = 4 # How many words to consider left and right.\n",
    "\n",
    "# The sparse matrix that stores the word co-occurences\n",
    "cooc_mat = lil_matrix((vocabulary_size, vocabulary_size), dtype=np.float32)\n",
    "\n",
    "print(cooc_mat.shape)\n",
    "def generate_cooc(batch_size,skip_window):\n",
    "    '''\n",
    "    Generate co-occurence matrix by processing batches of data\n",
    "    '''\n",
    "    data_index = 0\n",
    "    print('Running %d iterations to compute the co-occurance matrix'%(dataset_size//batch_size))\n",
    "    for i in range(dataset_size//batch_size):\n",
    "        # Printing progress\n",
    "        if i>0 and i%100000==0:\n",
    "            print('\\tFinished %d iterations'%i)\n",
    "            \n",
    "        # Generating a single batch of data\n",
    "        batch, labels, weights = generate_batch(batch_size, skip_window)\n",
    "        labels = labels.reshape(-1)\n",
    "        \n",
    "        # Incrementing the sparse matrix entries accordingly\n",
    "        for inp,lbl,w in zip(batch,labels,weights):            \n",
    "            cooc_mat[inp,lbl] += (1.0*w)\n",
    "\n",
    "# Generate the matrix\n",
    "generate_cooc(8,skip_window)    \n",
    "\n",
    "# Just printing some parts of co-occurance matrix\n",
    "print('Sample chunks of co-occurance matrix')\n",
    "\n",
    "\n",
    "# Basically calculates the highest cooccurance of several chosen word\n",
    "for i in range(10):\n",
    "    idx_target = i\n",
    "    \n",
    "    # get the ith row of the sparse matrix and make it dense\n",
    "    ith_row = cooc_mat.getrow(idx_target)     \n",
    "    ith_row_dense = ith_row.toarray('C').reshape(-1)        \n",
    "    \n",
    "    # select target words only with a reasonable words around it.\n",
    "    while np.sum(ith_row_dense)<10 or np.sum(ith_row_dense)>50000:\n",
    "        # Choose a random word\n",
    "        idx_target = np.random.randint(0,vocabulary_size)\n",
    "        \n",
    "        # get the ith row of the sparse matrix and make it dense\n",
    "        ith_row = cooc_mat.getrow(idx_target) \n",
    "        ith_row_dense = ith_row.toarray('C').reshape(-1)    \n",
    "        \n",
    "    print('\\nTarget Word: \"%s\"'%reverse_dictionary[idx_target])\n",
    "        \n",
    "    sort_indices = np.argsort(ith_row_dense).reshape(-1) # indices with highest count of ith_row_dense\n",
    "    sort_indices = np.flip(sort_indices,axis=0) # reverse the array (to get max values to the start)\n",
    "\n",
    "    # printing several context words to make sure cooc_mat is correct\n",
    "    print('Context word:',end='')\n",
    "    for j in range(10):        \n",
    "        idx_context = sort_indices[j]       \n",
    "        print('\"%s\"(id:%d,count:%.2f), '%(reverse_dictionary[idx_context],idx_context,ith_row_dense[idx_context]),end='')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GloVe Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Defining Hyperparameters\n",
    "\n",
    "Here we define several hyperparameters including `batch_size` (amount of samples in a single batch) `embedding_size` (size of embedding vectors) `window_size` (context window size)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "batch_size = 128 # Data points in a single batch\n",
    "embedding_size = 128 # Dimension of the embedding vector.\n",
    "window_size = 4 # How many words to consider left and right.\n",
    "\n",
    "# We pick a random validation set to sample nearest neighbors\n",
    "valid_size = 16 # Random set of words to evaluate similarity on.\n",
    "# We sample valid datapoints randomly from a large window without always being deterministic\n",
    "valid_window = 50\n",
    "\n",
    "# When selecting valid examples, we select some of the most frequent words as well as\n",
    "# some moderately rare words as well\n",
    "valid_examples = np.array(random.sample(range(valid_window), valid_size))\n",
    "valid_examples = np.append(valid_examples,random.sample(range(1000, 1000+valid_window), valid_size),axis=0)\n",
    "\n",
    "num_sampled = 32 # Number of negative examples to sample.\n",
    "\n",
    "epsilon = 1 # used for the stability of log in the loss function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defining Inputs and Outputs\n",
    "\n",
    "Here we define placeholders for feeding in training inputs and outputs (each of size `batch_size`) and a constant tensor to contain validation examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tf.reset_default_graph()\n",
    "\n",
    "# Training input data (target word IDs).\n",
    "train_dataset = tf.placeholder(tf.int32, shape=[batch_size])\n",
    "# Training input label data (context word IDs)\n",
    "train_labels = tf.placeholder(tf.int32, shape=[batch_size])\n",
    "# Validation input data, we don't need a placeholder\n",
    "# as we have already defined the IDs of the words selected\n",
    "# as validation data\n",
    "valid_dataset = tf.constant(valid_examples, dtype=tf.int32)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defining Model Parameters and Other Variables\n",
    "We now define four TensorFlow variables which is composed of an embedding layer, a bias for each input and output words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Variables.\n",
    "in_embeddings = tf.Variable(\n",
    "    tf.random_uniform([vocabulary_size, embedding_size], -1.0, 1.0),name='embeddings')\n",
    "in_bias_embeddings = tf.Variable(tf.random_uniform([vocabulary_size],0.0,0.01,dtype=tf.float32),name='embeddings_bias')\n",
    "\n",
    "out_embeddings = tf.Variable(\n",
    "    tf.random_uniform([vocabulary_size, embedding_size], -1.0, 1.0),name='embeddings')\n",
    "out_bias_embeddings = tf.Variable(tf.random_uniform([vocabulary_size],0.0,0.01,dtype=tf.float32),name='embeddings_bias')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defining the Model Computations\n",
    "\n",
    "We first defing a lookup function to fetch the corresponding embedding vectors for a set of given inputs. Then we define a placeholder that takes in the weights for a given batch of data points (`weights_x`) and co-occurence matrix weights (`x_ij`). `weights_x` measures the importance of a data point with respect to how much those two words co-occur and `x_ij` denotes the co-occurence matrix value for the row and column denoted by the words in a datapoint. With these defined, we can define the loss as shown below. For exact details refer Chapter 4 text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Look up embeddings for inputs and outputs\n",
    "# Have two seperate embedding vector spaces for inputs and outputs\n",
    "embed_in = tf.nn.embedding_lookup(in_embeddings, train_dataset)\n",
    "embed_out = tf.nn.embedding_lookup(out_embeddings, train_labels)\n",
    "embed_bias_in = tf.nn.embedding_lookup(in_bias_embeddings,train_dataset)\n",
    "embed_bias_out = tf.nn.embedding_lookup(out_bias_embeddings,train_labels)\n",
    "\n",
    "# weights used in the cost function\n",
    "weights_x = tf.placeholder(tf.float32,shape=[batch_size],name='weights_x') \n",
    "# Cooccurence value for that position\n",
    "x_ij = tf.placeholder(tf.float32,shape=[batch_size],name='x_ij')\n",
    "\n",
    "# Compute the loss defined in the paper. Note that \n",
    "# I'm not following the exact equation given (which is computing a pair of words at a time)\n",
    "# I'm calculating the loss for a batch at one time, but the calculations are identical.\n",
    "# I also made an assumption about the bias, that it is a smaller type of embedding\n",
    "loss = tf.reduce_mean(\n",
    "    weights_x * (tf.reduce_sum(embed_in*embed_out,axis=1) + embed_bias_in + embed_bias_out - tf.log(epsilon+x_ij))**2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculating Word Similarities \n",
    "We calculate the similarity between two given words in terms of the cosine distance. To do this efficiently we use matrix operations to do so, as shown below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Compute the similarity between minibatch examples and all embeddings.\n",
    "# We use the cosine distance:\n",
    "embeddings = (in_embeddings + out_embeddings)/2.0\n",
    "norm = tf.sqrt(tf.reduce_sum(tf.square(embeddings), 1, keepdims=True))\n",
    "normalized_embeddings = embeddings / norm\n",
    "valid_embeddings = tf.nn.embedding_lookup(\n",
    "normalized_embeddings, valid_dataset)\n",
    "similarity = tf.matmul(valid_embeddings, tf.transpose(normalized_embeddings))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model Parameter Optimizer\n",
    "\n",
    "We then define a constant learning rate and an optimizer which uses the Adagrad method. Feel free to experiment with other optimizers listed [here](https://www.tensorflow.org/api_guides/python/train)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Optimizer.\n",
    "optimizer = tf.train.AdagradOptimizer(1.0).minimize(loss)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running the GloVe Algorithm\n",
    "\n",
    "Here we run the GloVe algorithm we defined above. Specifically, we first initialize variables, and then train the algorithm for many steps (`num_steps`). And every few steps we evaluate the algorithm on a fixed validation set and print out the words that appear to be closest for a given set of words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0: 9.578778\n",
      "Nearest to it: karol, burgh, destabilise, armchair, crook, roguery, one-sixth, swains,\n",
      "Nearest to that: wmap, partake, ahmadi, armstrong, memberships, forza, director-general, condo,\n",
      "Nearest to has: mentality, vastly, approaches, bulwark, enzymes, originally, privatize, reunify,\n",
      "Nearest to but: inhabited, potrero, trust, memory, curran, philips, p.m.s, pagoda,\n",
      "Nearest to city: seals, counter-revolution, tubular, kayaking, central, 1568, override, buckland,\n",
      "Nearest to this: dispersion, intermarriage, dialysis, moguls, aldermen, alcoholic, codes, farallon,\n",
      "Nearest to UNK: 40.3, tatsam, jupiter, verify, unequal, berliners, march, 1559,\n",
      "Nearest to by: functionalists, synthesised, palladius, chiapas, synaptic, sumner, raining, valued,\n",
      "Nearest to or: amherst, 'mother, epiglottis, wen, stanislaus, trafford, cuticle, reminded,\n",
      "Nearest to been: 640,961., depression-era, uniquely, mami, 375,000, stickiness, medium-sized, amor,\n",
      "Nearest to with: anti-statist, pitigliano, branches, reparations, acquittal, frowned, pishpek, left-leaning,\n",
      "Nearest to be: i-20, kevin, greased, rightly, conductors, hypercholesterolemia, pedro, douaumont,\n",
      "Nearest to as: gabon, horda, mead, protruding, soundtrack, algeria, 48, macon,\n",
      "Nearest to at: kambula, tisa, spelled, 130,000, 2008, organisers, |jul_rec_lo_°f, arrows,\n",
      "Nearest to ,: is, of, its, malton, martinů, retiree, reliant, uri,\n",
      "Nearest to its: of, ,, galleon, gitlow, rugby-playing, varanasi, fono, clusters,\n",
      "Average loss at step 2000: 0.739107\n",
      "Average loss at step 4000: 0.091107\n",
      "Average loss at step 6000: 0.068614\n",
      "Average loss at step 8000: 0.076040\n",
      "Average loss at step 10000: 0.058149\n",
      "Nearest to it: was, is, that, not, a, in, to, .,\n",
      "Nearest to that: is, was, the, a, ., ,, to, in,\n",
      "Nearest to has: is, it, that, a, been, was, to, mentality,\n",
      "Nearest to but: with, said, trust, mating, not, squamous, war—the, r101,\n",
      "Nearest to city: of, 's, counter-revolution, the, professed, ., equilibrium, seals,\n",
      "Nearest to this: is, ., for, in, was, the, a, that,\n",
      "Nearest to UNK: and, ,, (, in, the, ., ), a,\n",
      "Nearest to by: the, and, ,, ., in, was, of, a,\n",
      "Nearest to or: UNK, ,, and, a, cuticle, donnchad, ``, 'mother,\n",
      "Nearest to been: have, had, to, has, be, was, that, it,\n",
      "Nearest to with: ,, and, a, the, in, of, for, .,\n",
      "Nearest to be: to, have, that, a, for, not, can, been,\n",
      "Nearest to as: a, ,, for, and, UNK, ``, is, in,\n",
      "Nearest to at: the, of, ., in, ,, and, 's, UNK,\n",
      "Nearest to ,: and, UNK, in, the, ., a, of, for,\n",
      "Nearest to its: compacted, for, puzzling, buddha, bjorn, d'etat, tēōtl, encapsulated,\n",
      "Average loss at step 12000: 0.048867\n",
      "Average loss at step 14000: 0.102374\n",
      "Average loss at step 16000: 0.047017\n",
      "Average loss at step 18000: 0.041279\n",
      "Average loss at step 20000: 0.065086\n",
      "Nearest to it: is, was, not, that, a, to, he, has,\n",
      "Nearest to that: is, was, the, a, to, ,, ., and,\n",
      "Nearest to has: it, been, was, a, is, that, to, .,\n",
      "Nearest to but: with, not, which, that, ,, said, mating, trust,\n",
      "Nearest to city: of, 's, the, ., in, counter-revolution, for, at,\n",
      "Nearest to this: ., is, was, for, in, the, it, of,\n",
      "Nearest to UNK: and, ,, (, ), in, the, a, .,\n",
      "Nearest to by: the, in, ,, and, was, ., of, a,\n",
      "Nearest to or: UNK, ,, a, and, (, ``, ), with,\n",
      "Nearest to been: have, had, has, be, to, was, that, not,\n",
      "Nearest to with: and, ,, a, of, the, in, for, UNK,\n",
      "Nearest to be: to, have, that, a, not, from, is, been,\n",
      "Nearest to as: a, ,, for, and, is, UNK, the, of,\n",
      "Nearest to at: the, ., of, in, 's, and, ,, by,\n",
      "Nearest to ,: and, UNK, in, the, a, ., of, with,\n",
      "Nearest to its: for, with, and, compacted, of, his, tēōtl, ,,\n",
      "Average loss at step 22000: 0.036469\n",
      "Average loss at step 24000: 0.037744\n",
      "Average loss at step 26000: 0.035548\n",
      "Average loss at step 28000: 0.035010\n",
      "Average loss at step 30000: 0.038970\n",
      "Nearest to it: is, was, not, that, has, he, a, this,\n",
      "Nearest to that: is, was, the, to, ,, ., a, and,\n",
      "Nearest to has: it, is, was, been, a, that, have, to,\n",
      "Nearest to but: which, with, not, ,, was, that, is, it,\n",
      "Nearest to city: of, 's, the, ., in, at, from, world,\n",
      "Nearest to this: is, ., was, in, for, it, the, a,\n",
      "Nearest to UNK: and, ,, (, ), in, ., the, a,\n",
      "Nearest to by: the, was, in, ,, and, ., of, a,\n",
      "Nearest to or: UNK, (, ,, ``, and, a, ), with,\n",
      "Nearest to been: have, had, has, be, to, was, that, not,\n",
      "Nearest to with: ,, and, a, of, the, in, ., UNK,\n",
      "Nearest to be: to, have, from, not, that, a, is, can,\n",
      "Nearest to as: a, ,, for, an, and, is, UNK, with,\n",
      "Nearest to at: the, of, ., in, 's, ,, and, UNK,\n",
      "Nearest to ,: and, UNK, in, the, ., a, with, of,\n",
      "Nearest to its: for, with, his, and, to, of, the, ,,\n",
      "Average loss at step 32000: 0.033023\n",
      "Average loss at step 34000: 0.031445\n",
      "Average loss at step 36000: 0.030053\n",
      "Average loss at step 38000: 0.028875\n",
      "Average loss at step 40000: 0.028649\n",
      "Nearest to it: is, was, not, that, has, a, also, he,\n",
      "Nearest to that: is, was, to, a, the, it, ,, .,\n",
      "Nearest to has: it, was, is, been, a, that, had, also,\n",
      "Nearest to but: which, not, with, that, ,, was, it, is,\n",
      "Nearest to city: 's, of, the, ., in, at, world, from,\n",
      "Nearest to this: is, ., was, in, for, it, the, a,\n",
      "Nearest to UNK: and, ,, ), (, in, the, ., a,\n",
      "Nearest to by: was, ,, the, in, and, ., of, to,\n",
      "Nearest to or: UNK, (, ,, a, ), and, ``, with,\n",
      "Nearest to been: have, had, has, be, to, was, not, that,\n",
      "Nearest to with: and, ,, a, of, the, in, for, UNK,\n",
      "Nearest to be: to, have, from, that, not, a, can, is,\n",
      "Nearest to as: a, ,, an, for, and, is, such, to,\n",
      "Nearest to at: the, ., of, in, 's, ,, by, and,\n",
      "Nearest to ,: and, UNK, in, the, a, ., with, of,\n",
      "Nearest to its: for, and, with, to, his, of, the, ,,\n",
      "Average loss at step 42000: 0.037198\n",
      "Average loss at step 44000: 0.027172\n",
      "Average loss at step 46000: 0.027344\n",
      "Average loss at step 48000: 0.028739\n",
      "Average loss at step 50000: 0.105829\n",
      "Nearest to it: is, was, that, not, has, he, also, a,\n",
      "Nearest to that: is, was, a, to, it, by, the, .,\n",
      "Nearest to has: it, is, been, was, that, a, have, had,\n",
      "Nearest to but: which, not, with, ,, it, that, was, is,\n",
      "Nearest to city: of, the, 's, ., in, from, at, is,\n",
      "Nearest to this: is, ., in, for, was, it, the, a,\n",
      "Nearest to UNK: (, and, ,, from, ., at, by, a,\n",
      "Nearest to by: the, ,, and, ., a, in, was, of,\n",
      "Nearest to or: ``, ), (, ,, a, with, and, '',\n",
      "Nearest to been: have, has, had, be, to, that, was, also,\n",
      "Nearest to with: and, ,, a, for, the, in, of, .,\n",
      "Nearest to be: to, have, not, from, a, that, is, can,\n",
      "Nearest to as: a, an, ,, for, is, and, to, such,\n",
      "Nearest to at: the, of, ., in, by, 's, ,, and,\n",
      "Nearest to ,: and, in, the, ., a, of, with, for,\n",
      "Nearest to its: for, with, and, ,, his, the, of, in,\n",
      "Average loss at step 52000: 0.111760\n",
      "Average loss at step 54000: 0.031062\n",
      "Average loss at step 56000: 0.070919\n",
      "Average loss at step 58000: 0.027815\n",
      "Average loss at step 60000: 0.025161\n",
      "Nearest to it: is, was, that, not, has, also, he, a,\n",
      "Nearest to that: is, was, it, to, the, ., a, by,\n",
      "Nearest to has: it, is, was, been, a, that, had, also,\n",
      "Nearest to but: which, not, with, ,, it, was, that, is,\n",
      "Nearest to city: 's, of, the, ., in, from, at, world,\n",
      "Nearest to this: is, ., was, in, it, for, the, at,\n",
      "Nearest to UNK: (, ), and, ,, the, a, by, .,\n",
      "Nearest to by: the, was, in, ., ,, and, of, is,\n",
      "Nearest to or: (, ), ,, a, ``, and, with, '',\n",
      "Nearest to been: have, has, had, be, was, also, that, to,\n",
      "Nearest to with: and, ,, a, of, in, for, the, .,\n",
      "Nearest to be: to, have, can, not, from, a, is, that,\n",
      "Nearest to as: a, an, ,, for, such, and, is, to,\n",
      "Nearest to at: the, ., of, in, 's, by, ,, is,\n",
      "Nearest to ,: and, in, the, ., a, with, of, for,\n",
      "Nearest to its: for, with, and, to, ,, of, the, his,\n",
      "Average loss at step 62000: 0.024341\n",
      "Average loss at step 64000: 0.024122\n",
      "Average loss at step 66000: 0.023625\n",
      "Average loss at step 68000: 0.023307\n",
      "Average loss at step 70000: 0.023168\n",
      "Nearest to it: is, was, not, that, has, also, a, he,\n",
      "Nearest to that: is, was, to, the, it, ., a, ,,\n",
      "Nearest to has: it, was, been, had, a, is, that, have,\n",
      "Nearest to but: which, not, with, ,, it, was, that, is,\n",
      "Nearest to city: of, 's, the, ., in, at, world, from,\n",
      "Nearest to this: is, ., was, in, it, for, the, at,\n",
      "Nearest to UNK: (, ), and, ,, by, or, the, in,\n",
      "Nearest to by: the, ,, was, ., and, in, of, a,\n",
      "Nearest to or: (, ), a, ,, and, ``, UNK, with,\n",
      "Nearest to been: have, has, had, be, was, also, to, that,\n",
      "Nearest to with: and, ,, a, the, in, of, for, .,\n",
      "Nearest to be: to, have, can, not, a, that, is, from,\n",
      "Nearest to as: a, an, for, ,, such, and, is, to,\n",
      "Nearest to at: the, of, ., in, 's, by, ,, is,\n",
      "Nearest to ,: and, in, the, ., a, of, with, for,\n",
      "Nearest to its: for, with, and, their, his, ,, of, the,\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average loss at step 72000: 0.022413\n",
      "Average loss at step 74000: 0.021599\n",
      "Average loss at step 76000: 0.021968\n",
      "Average loss at step 78000: 0.021922\n",
      "Average loss at step 80000: 0.021073\n",
      "Nearest to it: is, was, not, that, also, has, a, this,\n",
      "Nearest to that: is, was, it, to, ., the, ,, a,\n",
      "Nearest to has: it, been, was, is, also, that, had, a,\n",
      "Nearest to but: which, not, with, it, ,, was, that, and,\n",
      "Nearest to city: of, 's, the, ., in, at, world, from,\n",
      "Nearest to this: is, ., was, in, it, for, at, the,\n",
      "Nearest to UNK: (, ), and, ,, or, a, ., by,\n",
      "Nearest to by: the, ,, was, and, ., in, a, of,\n",
      "Nearest to or: (, UNK, a, ), ,, and, ``, with,\n",
      "Nearest to been: have, has, had, also, be, to, that, was,\n",
      "Nearest to with: ,, and, a, the, of, in, for, .,\n",
      "Nearest to be: to, have, can, not, from, that, is, a,\n",
      "Nearest to as: a, an, ,, such, for, and, ., is,\n",
      "Nearest to at: of, the, ., in, 's, ,, and, by,\n",
      "Nearest to ,: and, in, the, ., a, with, of, for,\n",
      "Nearest to its: for, and, with, their, ,, his, to, the,\n",
      "Average loss at step 82000: 0.021116\n",
      "Average loss at step 84000: 0.020798\n",
      "Average loss at step 86000: 0.020017\n",
      "Average loss at step 88000: 0.019837\n",
      "Average loss at step 90000: 0.019543\n",
      "Nearest to it: is, was, that, also, not, has, this, a,\n",
      "Nearest to that: was, is, to, the, ., it, a, ,,\n",
      "Nearest to has: it, been, was, is, a, had, also, that,\n",
      "Nearest to but: which, not, ,, with, it, was, and, that,\n",
      "Nearest to city: of, 's, the, ., in, new, world, at,\n",
      "Nearest to this: is, ., was, it, in, for, the, at,\n",
      "Nearest to UNK: (, and, ), ,, in, or, a, .,\n",
      "Nearest to by: the, was, ,, in, ., and, a, of,\n",
      "Nearest to or: (, UNK, ), ``, a, ,, and, with,\n",
      "Nearest to been: have, has, had, also, be, that, was, to,\n",
      "Nearest to with: and, ,, a, the, of, in, for, .,\n",
      "Nearest to be: to, have, can, not, that, from, is, would,\n",
      "Nearest to as: a, an, ,, such, for, and, is, the,\n",
      "Nearest to at: of, the, ., in, 's, ,, and, by,\n",
      "Nearest to ,: and, in, the, ., a, with, of, UNK,\n",
      "Nearest to its: for, and, their, with, his, ,, the, of,\n",
      "Average loss at step 92000: 0.019305\n",
      "Average loss at step 94000: 0.019555\n",
      "Average loss at step 96000: 0.019266\n",
      "Average loss at step 98000: 0.018803\n",
      "Average loss at step 100000: 0.018488\n",
      "Nearest to it: is, was, also, that, not, has, this, a,\n",
      "Nearest to that: was, is, to, it, the, a, ., ,,\n",
      "Nearest to has: it, been, was, had, also, is, that, a,\n",
      "Nearest to but: which, not, ,, it, with, was, and, a,\n",
      "Nearest to city: of, 's, the, ., in, is, new, world,\n",
      "Nearest to this: is, ., was, it, in, for, the, at,\n",
      "Nearest to UNK: (, and, ), ,, or, a, the, .,\n",
      "Nearest to by: the, ., was, ,, and, in, of, a,\n",
      "Nearest to or: UNK, (, ``, a, ), ,, and, with,\n",
      "Nearest to been: have, has, had, also, be, was, that, to,\n",
      "Nearest to with: and, ,, a, the, of, in, for, .,\n",
      "Nearest to be: to, have, can, not, would, from, that, a,\n",
      "Nearest to as: a, such, an, ,, for, is, and, to,\n",
      "Nearest to at: of, ., the, in, 's, by, ,, and,\n",
      "Nearest to ,: and, in, the, ., a, with, UNK, of,\n",
      "Nearest to its: for, their, and, with, his, ,, to, the,\n"
     ]
    }
   ],
   "source": [
    "num_steps = 100001\n",
    "glove_loss = []\n",
    "\n",
    "average_loss = 0\n",
    "with tf.Session(config=tf.ConfigProto(allow_soft_placement=True)) as session:\n",
    "    \n",
    "    tf.global_variables_initializer().run()\n",
    "    print('Initialized')\n",
    "    \n",
    "    for step in range(num_steps):\n",
    "        \n",
    "        # generate a single batch (data,labels,co-occurance weights)\n",
    "        batch_data, batch_labels, batch_weights = generate_batch(\n",
    "            batch_size, skip_window) \n",
    "        \n",
    "        # Computing the weights required by the loss function\n",
    "        batch_weights = [] # weighting used in the loss function\n",
    "        batch_xij = [] # weighted frequency of finding i near j\n",
    "        \n",
    "        # Compute the weights for each datapoint in the batch\n",
    "        for inp,lbl in zip(batch_data,batch_labels.reshape(-1)):     \n",
    "            point_weight = (cooc_mat[inp,lbl]/100.0)**0.75 if cooc_mat[inp,lbl]<100.0 else 1.0 \n",
    "            batch_weights.append(point_weight)\n",
    "            batch_xij.append(cooc_mat[inp,lbl])\n",
    "        batch_weights = np.clip(batch_weights,-100,1)\n",
    "        batch_xij = np.asarray(batch_xij)\n",
    "        \n",
    "        # Populate the feed_dict and run the optimizer (minimize loss)\n",
    "        # and compute the loss. Specifically we provide\n",
    "        # train_dataset/train_labels: training inputs and training labels\n",
    "        # weights_x: measures the importance of a data point with respect to how much those two words co-occur\n",
    "        # x_ij: co-occurence matrix value for the row and column denoted by the words in a datapoint\n",
    "        feed_dict = {train_dataset : batch_data.reshape(-1), train_labels : batch_labels.reshape(-1),\n",
    "                    weights_x:batch_weights,x_ij:batch_xij}\n",
    "        _, l = session.run([optimizer, loss], feed_dict=feed_dict)\n",
    "        \n",
    "        # Update the average loss variable\n",
    "        average_loss += l\n",
    "        if step % 2000 == 0:\n",
    "          if step > 0:\n",
    "            average_loss = average_loss / 2000\n",
    "          # The average loss is an estimate of the loss over the last 2000 batches.\n",
    "          print('Average loss at step %d: %f' % (step, average_loss))\n",
    "          glove_loss.append(average_loss)\n",
    "          average_loss = 0\n",
    "        \n",
    "        # Here we compute the top_k closest words for a given validation word\n",
    "        # in terms of the cosine distance\n",
    "        # We do this for all the words in the validation set\n",
    "        # Note: This is an expensive step\n",
    "        if step % 10000 == 0:\n",
    "          sim = similarity.eval()\n",
    "          for i in range(valid_size):\n",
    "            valid_word = reverse_dictionary[valid_examples[i]]\n",
    "            top_k = 8 # number of nearest neighbors\n",
    "            nearest = (-sim[i, :]).argsort()[1:top_k+1]\n",
    "            log = 'Nearest to %s:' % valid_word\n",
    "            for k in range(top_k):\n",
    "              close_word = reverse_dictionary[nearest[k]]\n",
    "              log = '%s %s,' % (log, close_word)\n",
    "            print(log)\n",
    "            \n",
    "    final_embeddings = normalized_embeddings.eval()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
